/*
    注意用的是优先级队列
    因此我们在弹出的时候标记元素被访问
    如果是普通队列在入队时进行标记
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
struct edge
{
    int w;
    int to;
    int next;
} edges[N];
int ind;
int head[N];
int n, m;
bool st[N];
int dis[N];
typedef pair<int, int> pp;
priority_queue<pp, vector<pp>, greater<pp>> q;
void add(int u, int v, int w)
{
    edges[ind].w = w;
    edges[ind].to = v;
    edges[ind].next = head[u];
    head[u] = ind++;
}
int dijkstra()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    q.push(make_pair(0, 1));

    while (q.size())
    {
        auto tem = q.top();
        q.pop();
        int curw = tem.first;
        int curnode = tem.second;
        if (!st[curnode])
        {
            st[curnode] = true;
            for (int i = head[curnode]; i != -1; i = edges[i].next)
            {
                int j = edges[i].to;
                // 这里如果我们已经选出的最小值加上权比dis[j]小就跟新
                if (dis[j] > dis[curnode] + edges[i].w)
                {
                    dis[j] = dis[curnode] + edges[i].w;
                    q.push(make_pair(dis[j], j));
                }
            }
        }
    }
    if (dis[n] == 0x3f3f3f3f)
        return -1;
    else
        return dis[n];
}
int main()
{
    memset(head, -1, sizeof head);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    cout << dijkstra();
    return 0;
}
